This invention relates generally to distributed networks, and more particularly to optimizing flow through a local-control network.
One of the primary goals of any communications system is to be able to optimize the flow of information through the system. Typically, a communication system may include a network of communication nodes through which data packets are transferred from a source node to a destination node. In order to be able to accomplish the above-stated goal, it is necessary to develop a methodology which determines the optimal routing of information through a network.
In the prior art, those who sought to determine the optimal flow of information through a communication system utilized flow theory directed to determining the maximum flow of any type of commodity through a distributed network. In a typical communication network, commodities are various data types such as text, voice, video graphics, etc., routed from a source node to a sink or destination node. A source node is a point within the distributed network at which some commodity originally exists. A sink node is another point within the network at which the same commodity is desired to be routed to. A distributed network may have many nodes, located within such network and configured such that a commodity must be routed through a number of these nodes in order to travel from the source node to the sink node.
FIG. 1 illustrates a part of a sample network, showing source node 10, which transfers data 60 to sink node 110 across edge 50a. Data divider 30 operates to divide data within the queues of source node 10, the purpose and method of which will be discussed in detail later. Queues 20, 20a and 120 of source node 10 and sink node 110, respectively, are memory spaces which store the data prior to transfer from one node to the other.
Each edge 50 has two queues connected to itxe2x80x94one at each end of the edge. Thus, an edge which connects one node and a neighboring node has one queue in the first node and the other queue in the second node. FIG. 1 shows edge 50a with two queues connected to it, namely queue 20a and queue 120. The other edges 50 are shown connected to the other queues 20 in source node 10. Though not shown, the other end of each of the other edges 50 is connected to a queue of a neighboring node. It should also be noted that in this figure, the source node and the sink node are situated adjacent to each other, such that they are not seperated from each other by several other nodes (as would be the case in the typical network flow problem), and are thus meant only to illustrate some of the features of a typical node within a distributed network.
FIG. 2, which will be explained more fully later, illustrates a mesh graph, having 14 nodes (of the type of node illustrated in FIG. 1) and 3 levels. This graph represents just one way in which a distributed network can be configured, although it is understood that there are countless other possible configurations. In particular, a mesh graph may be representative of an asynchronous transfer mode (hereinafter xe2x80x9cATMxe2x80x9d) network, in which commodities such as audio or video data are routed by switches through the ATM network across connections having pre-determined bandwidth. In this figure, the numbered circles are communication nodes, such as those employed in a computer communication network. As shown, the nodes are connected by arrows. The arrows show the manner in which the computer terminals are connected to each other and the directions in which they can transfer data through the network. Thus, for example, if a person using the computer terminal designated as node 14 desires data from a host computer terminal designated as node 1, the arrows represent the possible paths for the data to be transmitted from node 1 to node 14. In this example, the data is the commodity sought.
Alternatively, the communications system illustrated in FIG. 2 could also be representative of a fiber optic telephone network, in which each node is representative of a call switching station and each arrow is representative of a fiber optic cable over which a telephone call or data transmission may be sent. In this manner, a call (the commodity in this example), could be made from a telephone designated by node 1 (the xe2x80x9csourcexe2x80x9d node) to a telephone designated by node 14 (the xe2x80x9csinkxe2x80x9d node), and that call could be routed through the fiber optic network in any manner shown by the arrows.
FIG. 3 is provided to illustrate a sample of an RMF graph. The sample graph is a 3xc3x973xc3x972 RMF graph, showing another way in which a distributed network can be configured. As in the ATM network, the numbered circles represent nodes and the arrows represent edges over which desired information may be routed. Of course, it is understood that FIGS. 2 and 3 describe just two of many types and configurations of communications systems which could exist, and that a communication system is just one type of network which routes commodities between routing nodes.
Referring back to the prior art which sought to determine optimal flows through a network, in addition to a source node and a sink node, each commodity also has an associated demand, which is the amount of that commodity that must be transmitted from its source to its sink. When only one type of commodity exists in a distributed network, a problem called the max flow problem exists. The max flow problem is the question of how to maximize a feasible flow, of a single type of commodity, through a network from a source to a sink. A flow is feasible if the transfer rate satisfies the demand for the commodity while remaining within the network""s capacity constraints.
The network""s capacity constraints are expressed through constraints placed on the edges of the network. An edge, as shown and described previously, is the connection between two neighboring nodes over which an amount of commodity can be transferred. Thus, in the max flow problem, it is desired to find the maximum flow of the single commodity through the network that does not exceed the capacities of the edges. Referring to the examples of communications systems discussed above, the capacity of the edges of a computer or internet system may be the bandwidth or data transfer capabilities of the connections, while the capacity of the edges of the fiber optic system may be the number of optical strands in a fiber optics trunk cable, and total channel bandwidth between two nodes.
The prior art also considered multicommodity flow. Multicommodity flow is an arrangement wherein a network simultaneously transmits multiple types of commodities through a network such that the total amount of flow on each edge is no more than the flow capacity of the edge. Multicommodity flow arises in a wide variety of contexts, such as product distribution, traffic planning and scheduling problems, but particularly in packet-routing and communications systems, such as networks that route data, voice, audio, video graphics, etc.
An additional consideration for those seeking to optimize flow through a communication system is the problem presented by each node""s inability to monitor the flow at every other point in the network. Particularly, in packet-routing and communications systems employing a distributed network, it is typically necessary for each node of the network to be locally-controlled. A locally-controlled network is one in which each node communicates only with neighboring nodes and has no global knowledge of the network. Packet-routing and communications systems are typically locally-controlled, since it is impractical for each node of a packet-routing or communications network to have knowledge of the existing flow conditions between every node pair within the network. It is practical, however, for each node of a network to have knowledge of the existing flow conditions between itself and adjacent or neighboring nodes. Thus, local-control algorithms for analyzing multicommodity flow arrangements are appropriate to examine in the context of packet-routing and communications networks.
Local-control algorithms for the max flow and multicommodity flow have been designed previously, as shown in Baruch Awerbuch and Tom Leighton, xe2x80x9cA Simple Local-Control Approximation Algorithm for Multicommodity Flowxe2x80x9d, 1993, and xe2x80x9cImproved Approximation Algorithms for the Multicommodity Flow Problem and Local Competitive Routing in Dynamic Networksxe2x80x9d, 1994, both incorporated herein by reference. In the former, the authors describe a max flow algorithm, which is performed in successive iterations. During each iteration, four steps are performed in each node and on each edge of the network.
In the first step, d units of flow are added to the source node. In the second step, the flow is partitioned such that the flow that is currently in a node is divided equally among the local queues of the edges incident to the node. In the third step, flow is routed across the edge in an amount equal to the lesser value of either xcex94(e)/2 or c(e), where xcex94(e) is the difference in the amount of flow between the two queues, and c(e) is the capacity of the edge in the direction from the fuller to the emptier queue. Finally, in the fourth step, all flow that has reached the sink, or destination node, is removed from the network.
The method described by these four steps is referred to herein as the first-order max flow method. This method is very slow and can take thousands of iterations to reach an acceptable approximation of the exact maximum flow value. FIG. 4 shows the results of using a first-order max flow method in order to find the maximum flow for a 20-level mesh graph with 402 nodes and 1180 edges. The first-order max flow method requires more than 8000 iterations in order to come within one percent of the maximum flow value of 1826.
In the same reference, the authors also describe a multicommodity flow arrangement, given a network with N nodes, M edges and K commodities, wherein each edge has a capacity c(e) and each commodity i has a demand, di. Like the single commodity case, the algorithm in the multi-commodity case proceeds in rounds, each round consisting of four phases.
In the first phase, new flow is added to the sources, such that di units of commodity i are added to source node si. In the second phase, for each node v and each commodity i, the amount of commodity i that is currently in node v is partitioned evenly among the local queues of the incident edges. For each edge e, an attempt is made to balance the amount of each commodity between the two queues at the endpoints of the edge. Additionally, the system resolves the contention between different commodities for the capacities of each edge. In the third phase, any commodity that has reached the appropriate sink, or destination node, is removed from the network. Finally, in the fourth phase, each commodity is reallocated within each node so that all the queues for each commodity i are equal in each node. The method described by these four phases is called herein the first-order multi-commodity flow method. Similar to the first-order max-flow method, this prior art multi-commodity flow arrangement requires several thousand iterations in order to converge to an acceptable approximation of the exact maximum flow value.
In the second reference, the authors describe an alternate prior art method to determine the optimal flow of multiple commodities through a distributed network. This method involves a bounded queuesize local-control algorithm for routing multi-commodity flows in a dynamically changing distributed network. The algorithm described is similar to the algorithm described in the first reference. A significant difference, however, is the process of storing excess flow in an overflow buffer. Potentials are calculated for the source queue and the overflow buffer, and flow is pushed across the edges so as to minimize the total potential of the queues in each edge, subject to the edge""s capacity contraints.
These, and other algorithms for speeding the flow of commodities through networks, are notoriously slow. In many cases, thousands of iterations are required in order to find the flow amount which maximize the flow through the network.
Therefore, a need exists for a system and method which speeds up distributed single and multi-commodity flow in a distributed network.
In accordance with one embodiment of the invention, a system and method for directing the flow of a quantity of data or of a plurality of data types through a communication system is employed. The communication system, which can be a network, comprises a plurality of switches including a source and a sink, each of the switches connected to a neighboring switch by a communication link having a capacity, each of the links having a pair of queue buffers so that one queue buffer of each pair of queue buffers is located at each switch connected by a link.
For a single data type, a flow is added at a source. In each switch, the flow is partitioned evenly among the queue buffers of the communication links of each switch. An amount of flow is computed for each link as a function of a difference between the amount of data in each of the queue buffer pairs, and, as a function of a previous amount of flow between the queue buffer pairs. The computed amount of flow of the data is routed across each link, and the routed data is then removed when it reaches a sink or a destination node. This process is iteratively repeated until a maximum flow value is reached.
In accordance with another embodiment of the invention, the amount of flow is computed for each link as f=(xcex2)(xcex94(e)/2)+(xcex2xe2x88x921)(fxe2x80x2), wherein xcex94(e) is defined as the difference in an amount of data between a pair of queue buffers,fxe2x80x2 is the last previous amount of flow between the same pair of queue buffers, and xcex2 is a value between 1.0 and 2.0.
In the multi-data type case, a flow of a data type i is added at the source; in each switch, the flow of each type is partitioned evenly among the queue buffers of the links of each switch; a difference in the amount of a data type i between each of the queue buffers of a switch and the queue buffers of each neighboring node is computed as xcex2xe2x80x2i(e)=(xcex2)(xcex94(e))+(2.0)(xcex2xe2x88x921)(fxe2x80x2), wherein xcex94ixe2x80x2(e) is a weighted queue difference between the pair of queue buffers, fxe2x80x2 is a last previous amount of flow between the same pair of queue buffers, and xcex2 is a value between 1.0 and 2.0; an amount of flow fi of said data type i is routed across each said link such that xcexa31xe2x89xa6ixe2x89xa6Kfi (xcex94xe2x80x2i(e)xe2x88x92fi) is maximized subject to the capacity constraint xcexa3fixe2x89xa6c(e); and the data type i which arrives at the sink is removed from the system network. The process is iteratively repeated until a optimal flow for all data types is reached.
In another embodiment of the invention, the system and method, in the multi-data type case, resolves the contention between different data types for the capacity of a communication link by finding flow values for each data type so as to guarantee that the data types with the biggest queue buffer difference across a link will have a priority. In another embodiment of the invention, the system and method prioritizes data types with the biggest queue buffer difference across a link, subject to a normalization factor. In still another embodiment of the invention, the single or multi-data type flow is adjusted so as not to exceed the capacity of an link. In still another embodiment of the invention, the single or multi-data type flow is adjusted so as not to exceed the amount of a data available to be routed by the sending queue buffer.